package top.minuy.subject.leetcode._206;
/**
 * @author Minuy
 * @time 21:49
 * @date 2021/8/26
 */
public class Solution {
    public ListNode normal(ListNode head){
        // 三个节点的引用
        ListNode pre,cur,next;

        // 初始化引用，这里next要保证cur不为空才有，所以稍后处理
        cur = head;
        pre = null;

        // 直到没有要被处理的节点
        while (cur != null){
            // next引用，确保找得到旧链表
            next = cur.next;

            // 修改当前节点的next引用，引用到前面的元素
            cur.next = pre;

            // 经过上一步操作后，pre指向新的头节点
            pre = cur;
            // 指向下一个要处理的元素
            cur = next;
        }

        // 返回新链表的头结点
        return pre;
    }

    public ListNode recursive(ListNode head) {
        // 传入空链表处理
        if(head == null){
            return null;
        }
        // 处理到结尾了，返回整个链表
        if(head.next == null){
            return head;
        }
        // 获取之后处理好的链表
        ListNode rev = recursive(head.next);

        // 处理好的链表的尾结点的next指向head
        head.next.next = head;
        // head也反转到null
        head.next = null;
        // 返回新链表的头节点
        return rev;
    }

    public ListNode reverseList(ListNode head) {
       return recursive(head);
    }
}
